// https://www.lintcode.com/problem/longest-substring-without-repeating-characters/description
// 384. 最长无重复字符的子串
// 给定一个字符串，请找出其中无重复字符的最长子字符串。

// 样例
// 例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为 3。

// 对于，"bbbbb"，其无重复字符的最长子字符串为"b"，长度为1。

// 挑战
// O(n) 时间



class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    
    // 个
    int lengthOfLongestSubstring(string &s) {
        map<char, int> record;
        int maxLen = 0;
        int tmpLen = 0;
        int j = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            char c = s[i];
            if (record.find(c) != record.end())
            {
                int idx = record[c];
                maxLen = max(maxLen, tmpLen);
                tmpLen = i - idx - 1;
                while (j <= idx)
                {
                    record.erase(s[j++]); //前面的要去掉。可以用一个j一直记录
                }
            }
            record[c] = i;
            tmpLen++;
        }
        maxLen = max(maxLen, tmpLen);
        return maxLen;
    }
    
    // 法一：两个指针，滑动窗口
    // • Hash + 双指针
    // • 类似sliding window 一边增加 一边减少
    // int lengthOfLongestSubstring(string &s) {
    //     int j = 0;
    //     int record[256];
    //     memset(record, 0, sizeof(record));
    //     int ans = 0;
    //     for (int i = 0; i < s.length(); i++)
    //     {
    //         while (j < s.length() && record[s[j]] == 0)
    //         {
    //             record[s[j]] = 1;
    //             j++;
    //         }
    //         ans = max(ans, j - i);
    //         record[s[i]] = 0;
    //     }
    //     return ans;
    // }

    // 法二：每个位置记录它到前一个相同字符(如有)的长度
    // O(n) 时间
    // int lengthOfLongestSubstring(string &s) {
    //     int last[256]; 
    //     memset(last, -1, sizeof(last)); //初始化为-1
    //     int ans = 0, left = 0, len = s.length();
    //     for (int i = 0; i < len; i++)
    //     {
    //         // if (last[s[i]] > left
    //         if (last[s[i]] >= left)
    //         {
    //             left = last[s[i]] + 1; // 直接更新left，因为子串重复就会导致重复
    //         }
    //         last[s[i]] = i;
    //         ans = max(ans, i - left + 1);
    //     }
    //     return ans;
    // }
};

